#include "Interval.h"
#include <boost/graph/transitive_closure.hpp>
#include <boost/graph/topological_sort.hpp>
// constructor

Interval::Interval(Graph& graph) : g(graph), helper(g)
{
	//helper.mergeStronglyCC();
}
// find the optimal tree cover, according to Agrawal's paper

void Interval::findOptTree()
{
	// compute the transtive closure
	Graph tc;
	VertexIndexMap index_map = get(&VertexProp::id, g);
	std::vector<Vertex> to_tc_vec(num_vertices(g));
	iterator_property_map < Vertex *, VertexIndexMap, Vertex, Vertex&>
		g_to_tc_map(&to_tc_vec[0], index_map);
	transitive_closure(g, tc, g_to_tc_map, index_map);
	std::vector<Vertex> topo;
	try
	{
		topological_sort(g, std::back_inserter(topo), vertex_index_map(get(&VertexProp::id, g)));
	}
	catch (not_a_dag)
	{
		cout << "Error: Not a DAG for topological sort" << endl;
		assert(false);
	}
	Vertex src;
	Edge e, tedge;
	// store tree edge
	int max_anc;
	int indgr;
	size_t idx;
	graph_traits<Graph>::in_edge_iterator ei, eiend;
	std::vector<Vertex>::reverse_iterator ri;
	for (ri = topo.rbegin(); ri != topo.rend(); ++ri)
	{
		//cout << vindex[*ri] << endl;
		// no incoming edge
		if (in_degree(*ri, g) == 0)
		{
			continue;
		}
		max_anc = -1;
		for (tie(ei, eiend) = in_edges(*ri, g); ei != eiend; ++ei)
		{
			e = *ei;
			g[e].tree = false;
			// assume all are non-tree edges
			src = source(e, g);
			// get source
			idx = g[src].id;
			indgr = in_degree(vertex(idx, tc), tc);
			// corresponding v in tc
			if (max_anc < indgr)
			{
				max_anc = indgr;
				tedge = e;
				// its source node has max ancestors
			}
		}
		g[tedge].tree = true;
		// mark tree edge
	}
	tc.clear();
}

int Interval::createTreeLabels(bool display)
{
	// find opt tree
	findOptTree();
	// get roots
	helper.getRoots(roots);
	// assign labels
	helper.assignIntervals(roots);
	// assign labels
	vector<Vertex> topo;
	try
	{
		topological_sort(g, std::back_inserter(topo),
						 vertex_index_map(get(&VertexProp::id, g)));
	}
	catch (not_a_dag)
	{
		cout << "Error: Not a DAG for topological sort" << endl;
		assert(false);
	}
	vector<Vertex>::iterator ri;
	map< int, PairSet >::iterator it2;
	PairSet::iterator c_it, p_it;
	// child_iterator, parent_iterator
	Vertex v, w;
	Edge e;
	PairSet ps;
	int c_begin, c_end;
	int p_begin, p_end;
	bool contain;
	graph_traits<Graph>::out_edge_iterator ei, eiend;
	// from the leaf level back to the root
	// since all children have been assigned intervals
	for (ri = topo.begin(); ri != topo.end(); ++ri)
	{
		v = *ri;
		ps.clear();
		ps.insert(make_pair(g[v].begin, g[v].end));
		for (p_it = ps.begin(); p_it != ps.end();)
		{
			p_begin = p_it->first;
			p_end = p_it->second;
			for (c_it = ps.begin(); c_it != ps.end();)
			{
				if (c_it == p_it)
				{
					++c_it;
					continue;
				}
				c_begin = c_it->first;
				c_end = c_it->second;
				if ((p_begin <= c_begin) && (c_end <= p_end))
					ps.erase(c_it++);
				else
					++c_it;
			}
			p_it++;
		}
		intervals.insert(make_pair(g[v].id, ps));
	}
	if (display)
		displayLabels();
	map< int, PairSet >::iterator it;
	int count = 0;
	for (it = intervals.begin(); it != intervals.end(); ++it)
	{
		count += it->second.size();
	}
	//cout << "total interval label size (# of integers):" << (count*2) << endl;
	return count;
}

int Interval::createLabels(bool display)
{
	//find opt tree
	findOptTree();
	//get roots
	helper.getRoots(roots);
	//assign labels
	helper.assignIntervals(roots);
	//assign labels
	vector<Vertex> topo;
	try
	{
		topological_sort(g, std::back_inserter(topo),
						 vertex_index_map(get(&VertexProp::id, g)));
	}
	catch (not_a_dag)
	{
		cout << "Error: Not a DAG for topological sort" << endl;
		assert(false);
	}
	vector<Vertex>::iterator ri;
	map< int, PairSet >::iterator it2;
	PairSet::iterator c_it, p_it;
	// child_iterator, parent_iterator
	Vertex v, w;
	Edge e;
	PairSet ps;
	int c_begin, c_end;
	int p_begin, p_end;
	bool contain;
	graph_traits<Graph>::out_edge_iterator ei, eiend;
	// from the leaf level back to the root
	// since all children have been assigned intervals
	for (ri = topo.begin(); ri != topo.end(); ++ri)
	{
		v = *ri;
		ps.clear();
		ps.insert(make_pair(g[v].begin, g[v].end));
		// add all intervals of its children
		for (tie(ei, eiend) = out_edges(v, g); ei != eiend; ++ei)
		{
			e = *ei;
			w = target(e, g);
			it2 = intervals.find(g[w].id);
			assert(it2 != intervals.end());
			// insert ranges
			for (c_it = it2->second.begin(); c_it != it2->second.end(); ++c_it)
			{
				c_begin = c_it->first;
				c_end = c_it->second;
				contain = false;
				for (p_it = ps.begin(); p_it != ps.end(); ++p_it)
				{
					p_begin = p_it->first;
					p_end = p_it->second;
					if (p_begin <= c_begin && c_end <= p_end)
					{
						contain = true;
						break;
					}
				}
				if (contain)
					continue;
				ps.insert(make_pair(c_begin, c_end));
			}
		}
		for (p_it = ps.begin(); p_it != ps.end();)
		{
			p_begin = p_it->first;
			p_end = p_it->second;
			for (c_it = ps.begin(); c_it != ps.end();)
			{
				if (c_it == p_it)
				{
					++c_it;
					continue;
				}
				c_begin = c_it->first;
				c_end = c_it->second;
				if ((p_begin <= c_begin) && (c_end <= p_end))
					ps.erase(c_it++);
				else
					++c_it;
			}
			p_it++;
		}
		intervals.insert(make_pair(g[v].id, ps));
	}
	if (display)
		displayLabels();
	map< int, PairSet >::iterator it;
	int count = 0;
	for (it = intervals.begin(); it != intervals.end(); ++it)
	{
		count += it->second.size();
	}
	cout << "total interval label size (# of integers):" << (count * 2) << endl;
	return count;
}

int Interval::createNonTreeLabels(bool display)
{
	// find opt tree
	findOptTree();
	// get roots
	helper.getRoots(roots);
	// assign labels
	helper.assignIntervals(roots);
	// assign labels
	vector<Vertex> topo;
	try
	{
		topological_sort(g, std::back_inserter(topo),
						 vertex_index_map(get(&VertexProp::id, g)));
	}
	catch (not_a_dag)
	{
		cout << "Error: Not a DAG for topological sort" << endl;
		assert(false);
	}
	vector<Vertex>::iterator ri;
	map< int, PairSet >::iterator it2;
	PairSet::iterator c_it, p_it;
	// child_iterator, parent_iterator
	Vertex v, w;
	Edge e;
	PairSet non_tree_ps;
	int c_begin, c_end;
	int p_begin, p_end;
	bool contain;
	graph_traits<Graph>::out_edge_iterator ei, eiend;
	// from the leaf level back to the root, since all children have been assigned intervals
	for (ri = topo.begin(); ri != topo.end(); ++ri)
	{
		v = *ri;
		non_tree_ps.clear();
		//we do not count tree intervals here.
		//non_tree_ps.insert( make_pair( g[v].begin, g[v].end  ) );
		// add all non-tree intervals of its children
		for (tie(ei, eiend) = out_edges(v, g); ei != eiend; ++ei)
		{
			e = *ei;

			w = target(e, g);
			// discard if tree edges
			if (g[v].begin < g[w].begin && g[v].end >= g[w].end) // (v -> w) is a non tree edge, add w's tree interval to v
			{
				//cout << g[v].id << "(" << g[v].begin << "," << g[v].end << ") needs" << g[w].id << "(" << g[w].begin << "," << g[w].end << ")" << endl;
			}
			else
				non_tree_ps.insert(make_pair(g[w].begin, g[w].end));
			// insert ranges
			//cout << "successor:" << g[w].id << endl;
			it2 = intervals.find(g[w].id);
			assert(it2 != intervals.end()); // test g[w]'s non-tree interval set is not empty
			//if not empty, then propogate them to its ancestors
			for (c_it = it2->second.begin(); c_it != it2->second.end(); ++c_it)
			{
				c_begin = c_it->first; // start
				c_end = c_it->second; // end
				contain = false;
				if (c_begin >= g[v].begin && c_end <= g[v].end) // already contained v's tree interval
					continue;
				for (p_it = non_tree_ps.begin(); p_it != non_tree_ps.end(); ++p_it)
				{
					p_begin = p_it->first;
					p_end = p_it->second;
					// if range is already contained in parent's range
					if (p_begin <= c_begin && c_end <= p_end)
					{
						contain = true;
						//cout << "(" << c_begin << ", " << c_end << ") is contained by " << g[v].id<< endl;
						break;
					}
				}
				if (contain) // if range already contained, skip it
					continue;
				non_tree_ps.insert(make_pair(c_begin, c_end));
				//cout << "(" << c_begin << ", " << c_end << ") is inserted to " <<g[v].id << endl;
			}
		}

		//////why this block?   remove redundant intervals!
		for (p_it = non_tree_ps.begin(); p_it != non_tree_ps.end();)
		{
			p_begin = p_it->first;
			p_end = p_it->second;
			for (c_it = non_tree_ps.begin(); c_it != non_tree_ps.end();)
			{
				if (c_it == p_it)
				{
					++c_it;
					continue;
				}
				c_begin = c_it->first;
				c_end = c_it->second;
				if ((p_begin <= c_begin) && (c_end <= p_end))
				{
					non_tree_ps.erase(c_it++);
					// cout << c_begin << "," << c_end << ", " << p_begin << ":" << p_end << endl;
				}
				else
					++c_it;
			}
			p_it++;
		}
		intervals.insert(make_pair(g[v].id, non_tree_ps));
	}
	//DEBUG count size
	if (display)
		displayLabels();
	map< int, PairSet >::iterator it;
	int count = 0;
	for (it = intervals.begin(); it != intervals.end(); ++it)
	{
		count += it->second.size();
	}
	//cout << "# of  uncoverd TC :" << (count) << endl;
	return count;
}
//assign Non tree intervals to special nodes (I, O nodes, i.e. exlcude normal nodes)

int Interval::createNonTreeLabels1(bool display)
{
	int size = 0;
	// find opt tree
	findOptTree();
	// get roots
	helper.getRoots(roots);
	// assign labels
	helper.assignIntervals(roots);
	// assign labels
	vector<Vertex> topo;
	try
	{
		topological_sort(g, std::back_inserter(topo),
						 vertex_index_map(get(&VertexProp::id, g)));
	}
	catch (not_a_dag)
	{
		cout << "Error: Not a DAG for topological sort" << endl;
		assert(false);
	}
	vector<Vertex>::iterator ri;
	map< int, PairSet >::iterator it2;
	PairSet::iterator c_it, p_it;
	// child_iterator, parent_iterator
	Vertex v, w;
	Edge e;
	PairSet non_tree_ps;
	int c_begin, c_end;
	int p_begin, p_end;
	bool contain;
	graph_traits<Graph>::out_edge_iterator ei, eiend;
	// from the leaf level back to the root, since all children have been assigned intervals
	for (ri = topo.begin(); ri != topo.end(); ++ri)
	{
		v = *ri;
		non_tree_ps.clear();
		//we do not count tree intervals here.
		//non_tree_ps.insert( make_pair( g[v].begin, g[v].end  ) );
		// add all non-tree intervals of its children
		for (tie(ei, eiend) = out_edges(v, g); ei != eiend; ++ei)
		{
			e = *ei;
			w = target(e, g);
			// discard if tree edges
			if (g[v].begin < g[w].begin && g[v].end >= g[w].end) // (v -> w) is a non tree edge, add w's tree interval to v
			{
				//cout << g[v].id << "(" << g[v].begin << "," << g[v].end << ") needs" << g[w].id << "(" << g[w].begin << "," << g[w].end << ")" << endl;
			}
			else
				non_tree_ps.insert(make_pair(g[w].begin, g[w].end));
			// insert ranges
			it2 = intervals.find(g[w].id);
			assert(it2 != intervals.end()); // test g[w]'s non-tree interval set is not empty
			//if not empty, then propogate them to its ancestors
			for (c_it = it2->second.begin(); c_it != it2->second.end(); ++c_it)
			{
				c_begin = c_it->first; // start
				c_end = c_it->second; // end
				contain = false;
				if (c_begin >= g[v].begin && c_end <= g[v].end) // already contained v's tree interval
					continue;
				for (p_it = non_tree_ps.begin(); p_it != non_tree_ps.end(); ++p_it)
				{
					p_begin = p_it->first;
					p_end = p_it->second;
					// if range is already contained in parent's range
					if (p_begin <= c_begin && c_end <= p_end)
					{
						contain = true;
						//cout << "(" << c_begin << ", " << c_end << ") is contained by " << g[v].id<< endl;
						break;
					}
				}
				if (contain) // if range already contained, skip it
					continue;
				non_tree_ps.insert(make_pair(c_begin, c_end));
				//cout << "(" << c_begin << ", " << c_end << ") is inserted to " <<g[v].id << endl;
			}
		}

		//////why this block?   remove redundant intervals!
		for (p_it = non_tree_ps.begin(); p_it != non_tree_ps.end();)
		{
			p_begin = p_it->first;
			p_end = p_it->second;
			for (c_it = non_tree_ps.begin(); c_it != non_tree_ps.end();)
			{
				if (c_it == p_it)
				{
					++c_it;
					continue;
				}
				c_begin = c_it->first;
				c_end = c_it->second;
				if ((p_begin <= c_begin) && (c_end <= p_end))
				{
					non_tree_ps.erase(c_it++);
					// cout << c_begin << "," << c_end << ", " << p_begin << ":" << p_end << endl;
				}
				else
					++c_it;
			}
			p_it++;
		}
		intervals.insert(make_pair(g[v].id, non_tree_ps));
		if (has_non_tree_edge(v))
			size += non_tree_ps.size();
	}
	//DEBUG count size
	if (display) displayLabels();
	map< int, PairSet >::iterator it;
	int count = 0;
	for (it = intervals.begin(); it != intervals.end(); ++it)
	{
		count += it->second.size();
	}
	//cout << "# of  uncoverd TC :" << (count) << endl;
	return size;
}

bool Interval::has_non_tree_edge(Vertex v)
{
	//int result = 0;
	if (in_degree(v, g) > 1)
		return true;
	//result += 1;
	graph_traits<Graph>::out_edge_iterator ei, eiend;
	for (tie(ei, eiend) = out_edges(v, g); ei != eiend; ++ei)
	{
		if (!g[*ei].tree)
		{
			//result +=2;break;
			return true;
		}
	}
	return false;
}

// create non-tree labels (no redundant, do not propogate non-tree intervals  via tree-edges)

int Interval::createNonTreeLabels2(bool display)
{
	// find opt tree
	findOptTree();
	// get roots
	helper.getRoots(roots);
	// assign labels
	helper.assignIntervals(roots);
	// assign labels
	vector<Vertex> topo;
	try
	{
		topological_sort(g, std::back_inserter(topo), vertex_index_map(get(&VertexProp::id, g)));
	}
	catch (not_a_dag)
	{
		cout << "Error: Not a DAG for topological sort" << endl;
		assert(false);
	}
	vector<Vertex>::iterator ri;
	map< int, PairSet >::iterator it2;
	PairSet::iterator c_it, p_it;
	// child_iterator, parent_iterator
	Vertex v, w;
	Edge e;
	PairSet non_tree_ps;
	int c_begin, c_end;
	int p_begin, p_end;
	bool contain;
	graph_traits<Graph>::out_edge_iterator ei, eiend;
	// from the leaf level back to the root, since all children have been assigned intervals
	for (ri = topo.begin(); ri != topo.end(); ++ri)
	{
		v = *ri;
		non_tree_ps.clear();
		//we do not count tree intervals here.
		//non_tree_ps.insert( make_pair( g[v].begin, g[v].end  ) );
		// add all non-tree intervals of its children
		for (tie(ei, eiend) = out_edges(v, g); ei != eiend; ++ei)
		{
			e = *ei;
			w = target(e, g);
			// add non-tree edges
			if (g[v].begin <= g[w].begin && g[v].end >= g[w].end)// (v -> w) is a non tree edge, add w's tree interval to v, we do not inherit intervals via tree-edges anymore
				continue;
			else
			{
				non_tree_ps.insert(make_pair(g[w].begin, g[w].end));
				//cout << g[v].id << "(" << g[v].begin << "," << g[v].end << ") needs" << g[w].id << "(" << g[w].begin << "," << g[w].end << ")" << endl;
				// insert ranges
				//cout << "successor:" << g[w].id << endl;
				it2 = intervals.find(g[w].id);
				assert(it2 != intervals.end()); // test g[w]'s non-tree interval set is not empty
				//if not empty, then propogate them to its ancestors
				for (c_it = it2->second.begin(); c_it != it2->second.end(); ++c_it)
				{
					c_begin = c_it->first; // start
					c_end = c_it->second; // end
					contain = false;
					if (c_begin >= g[v].begin && c_end <= g[v].end) // already contained by v's tree interval
						continue;
					for (p_it = non_tree_ps.begin(); p_it != non_tree_ps.end(); ++p_it)
					{
						p_begin = p_it->first;
						p_end = p_it->second;
						// if range is already contained in parent's range
						if (p_begin <= c_begin && c_end <= p_end)
						{
							contain = true;
							//cout << "(" << c_begin << ", " << c_end << ") is contained by " << g[v].id<< endl;
							break;
						}
					}
					if (contain) // if range already contained, skip it
						continue;
					non_tree_ps.insert(make_pair(c_begin, c_end));
					//cout << "(" << c_begin << ", " << c_end << ") is inserted to " <<g[v].id << endl;
				}
			}
		}

		//////why this block?   remove redudant intervals!
		/*
	for( p_it = non_tree_ps.begin(); p_it != non_tree_ps.end(); ) 
	{
		p_begin = p_it->first;
		p_end = p_it->second;
		for( c_it = non_tree_ps.begin(); c_it != non_tree_ps.end(); )
		{
		if( c_it == p_it ) 
		{
			++c_it;
			continue;
		}
		c_begin = c_it->first;
		c_end = c_it->second;	
		if( (p_begin <= c_begin) && (c_end <= p_end) )
		{
			non_tree_ps.erase( c_it++ );
			// cout << c_begin << "," << c_end << ", " << p_begin << ":" << p_end << endl;
		}
		else
			++c_it;
		}
		p_it++;
	}*/
		intervals.insert(make_pair(g[v].id, non_tree_ps));
	}
	//DEBUG count size
	if (display)
		displayLabels();
	map< int, PairSet >::iterator it;
	int count = 0;
	for (it = intervals.begin(); it != intervals.end(); ++it)
	{
		count += it->second.size();
	}
	//    cout << "# of interval labels:" << count << endl;
}


// display function
// for debug

void Interval::displayLabels()
{
	int tc_num = 0;
	map< int, PairSet >::iterator it;
	PairSet::iterator pos;
	for (it = intervals.begin(); it != intervals.end(); ++it)
	{
		cout << it->first << " --> ";
		for (pos = it->second.begin(); pos != it->second.end(); ++pos)
		{
			cout << "[" << pos->first << ", " << pos->second << "] ";
			tc_num += pos->second - pos->first + 1;
		}
		cout << endl;
	}
	cout << "Covered TC entries is " << tc_num << endl;
}

// evaluate whether u can reach v or not

bool Interval::reachable(Vertex u, Vertex v)
{

	map< int, PairSet >::iterator it;
	PairSet::iterator u_it, v_it;
	bool contain;
	int begin, end;
	// get labels of u and v
	it = intervals.find(g[u].id);
	assert(it != intervals.end());
	PairSet& uin = it->second;
	it = intervals.find(g[v].id);
	assert(it != intervals.end());
	PairSet& vin = it->second;
	for (v_it = vin.begin(); v_it != vin.end(); ++v_it)
	{
		begin = v_it->first;
		end = v_it->second;
		contain = false;
		for (u_it = uin.begin(); u_it != uin.end(); ++u_it)
		{
			if ((u_it->first <= begin) && (end <= u_it->second))
			{
				contain = true;
				break;
			}
		}
		if (!contain)
		{
			return false;
		}
	}
	return true;
}
// evaluate whether u can reach v or not

bool Interval::reachable(int u, int v)
{

	map< int, PairSet >::iterator it;
	PairSet::iterator u_it, v_it;
	bool contain;
	int begin, end;
	// get labels of u and v
	it = intervals.find(u);
	assert(it != intervals.end());
	PairSet& uin = it->second;
	it = intervals.find(v);
	assert(it != intervals.end());
	PairSet& vin = it->second;
	for (v_it = vin.begin(); v_it != vin.end(); ++v_it)
	{
		begin = v_it->first;
		end = v_it->second;
		contain = false;
		for (u_it = uin.begin(); u_it != uin.end(); ++u_it)
		{
			if ((u_it->first <= begin) && (end <= u_it->second))
			{
				contain = true;
				break;
			}
		}
		if (!contain)
		{
			return false;
		}
	}
	return true;
}

void Interval::testReach(int test_size)
{
	vector<Vertex> nodes;
	int gsize = num_vertices(g); // get the graph size
	graph_traits<Graph>::vertex_iterator vi, vi_end;
	for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
	{
		nodes.push_back(*vi); // store each vertex into a vector
	}
	int s, t; // source and target index
	int left = test_size;
	bool r1;
	while (left > 0)
	{
		// randomly generate a query
		s = rand() % gsize;
		t = rand() % gsize;
		if (s == t)
		{ // not to test the same node
			continue;
		}
		r1 = reachable(nodes[s], nodes[t]);
		left--;
	}
}
